#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>



/*--------------------Compter les occurences---------------------*/
void compter_occ(unsigned int carac[], char nom[])
{
	FILE *F; /* Fichier � partir duquel seront compt�es les occurences */
	int charlu; /* Caract�re courant lu dans le fichier */
//	unsigned int taille=0; /* Taille du fichier en octets*/

	/* Ouverture du fichier */
	if( (F = fopen(nom,"rb")) == NULL )
	{
		perror("Erreur => ouverture du fichier ");
		exit(EXIT_FAILURE);
	}

	while((charlu=fgetc(F))!=EOF)
		carac[charlu]++; /* Incrementation de la case correspondante au caract�re */

	fclose(F);
}


/*-------------------Cr�ation de l'arbre--------------------*/
struct arbre_huff * creer_arbre(unsigned int arbreN[])
{
	unsigned int i;
	struct temp_huff tmp;
	struct arbre_huff *arbre;
	unsigned int cpt_max=0;

	/* Initialisation */
	tmp.restant=0;

	for (i=0;i<MAXCAR;i++)
	{
		/* On enl�ve les caract�res qui ne sont pas dans le fichier */
		if (!arbreN[i])
			continue;

		/* Insertion dans l'arbre de chaque caract�re */
		if(!(arbre=malloc(sizeof(*arbre))))
		{
			perror("Erreur => fonction creer_arbre() ");
			exit(EXIT_FAILURE);
		}
		/* Remplissage des feuilles */
		arbre->c=(char)i;
		arbre->gauche=NULL;
		arbre->droite=NULL;
		arbre->occurence=arbreN[i];
		if((arbre->occurence)>cpt_max) /* On garde en m�moire le nombre d'occurence max */
			cpt_max=arbre->occurence;
		ajouter_temp_huff(&tmp,arbre);
	}


	while(tmp.restant>1) /* Tant que l'on a pas la racine de l'arbre */
	{
		if (!(arbre=malloc(sizeof(*arbre))))
		{
			perror("Erreur => malloc() fonction creer_arbre() ");
			exit(EXIT_FAILURE);
		}
		arbre->gauche=nouveau_noeud(&tmp);
		arbre->droite=nouveau_noeud(&tmp) ;
		arbre->occurence=arbre->gauche->occurence + arbre->droite->occurence; /* Le nouveau noeud cr�e � pour poids la somme des deux pr�c�dents */

		ajouter_temp_huff(&tmp,arbre);
	}

	/* On poss�de maintenant juste la racine de l'arbre */
	arbre=nouveau_noeud(&tmp);
	return arbre;
}

/*-----------------------Recherche du caract�re dans l'arbre-------------*/
struct arbre_huff * convert_huff(struct arbre_huff *arbre, unsigned int buffer, unsigned int buffer_taille, unsigned int niveau)
{
	if(niveau>buffer_taille) /* Si il n'y a pas assez de bits pour faire un caract�re */
		return NULL;

	if((arbre->gauche==NULL)&&(arbre->droite==NULL)) /* Le caract�re a �t� trouv� */
		return arbre;

	/* Si le dernier chiffre est un 0 on part � gauche */
	if((arbre->gauche!=NULL) && !((buffer >> (buffer_taille - niveau-1))&1))
		return convert_huff(arbre->gauche,buffer,buffer_taille,niveau+1);

	/* Si le dernier chiffre est un 1 on part � droite */
	if((arbre->droite!=NULL) && ((buffer >> (buffer_taille - niveau-1))&1))
		return convert_huff(arbre->droite,buffer,buffer_taille,niveau+1);

	return NULL; /* Si le code n'existe pas dans l'arbre */
}

/*---------------------Ajouter_temp_huf------------------------------*/
void ajouter_temp_huff(struct temp_huff *tmp, struct arbre_huff *arbre)
{
	int i;

	/* Recherche de la position ou inserer */
	for(i=tmp->restant;(tmp->noeud[i-1]->occurence)<(arbre->occurence);)
	{
		tmp->noeud[i]=tmp->noeud[i-1];
		if(!(--i))
			break;
	}
	/* Insertion des noeuds de l'arbre */
	tmp->noeud[i]=arbre;
	tmp->restant++;
}

/*--------------Recuparation de la valeur ayant la plus faible occurence--------*/
struct arbre_huff * nouveau_noeud(struct temp_huff *tmp)
{
	/* On teste que le fichier n'est pas vide */
	if(tmp->restant==0)
	{
		perror("Le fichier ne contient aucune donn�e ");
		exit(EXIT_FAILURE);
	}
	(tmp->restant)--;
	return tmp->noeud[tmp->restant];
}



/*----------------------Suppression de l'arbre de Huffman---------------------*/
void suppr_arbre(struct arbre_huff **arbre)
{
	if((*arbre)->gauche && (*arbre)->droite)
	{
		suppr_arbre(&(*arbre)->gauche);
		suppr_arbre(&(*arbre)->droite);
		free(*arbre);
		*arbre=NULL;
	}
}





